
import java.util.*;

class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int val) {
        this.val = val;
    }

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode (int val){
        this.val=val;
    }
}
  public class TestDemo13A {
    public static int MoreThanHalfNum_Solution(int []array){
        if(array==null||array.length==0){
            return 0;
        }
        int target=array[0];
        int times=1;
        for(int i=1;i<array.length;i++){
            if(times==0){
                target=array[i];
                times=1;
            }
            else if(target==array[i]){
                times++;
            }else {
                times--;
            }
        }
        int count=0;
        for(int i=0;i<array.length;i++){
            if(target==array[i]){
                count++;
            }
        }
        return count>array.length/2?count:0;
    }

    public static void main1(String[] args) {
        int []array={2,2,3,2,5,4};
        int tem=MoreThanHalfNum_Solution(array);
        System.out.println(tem);
    }
//给点字符串讲空格的部分变成%20
    public static String  replaceSpace(StringBuilder str){
        int count=0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)==' '){//记录空格有多少个
                count++;
            }
        }
        int new_length= str.length()+2*count;//扩增后新字符串的长度
        int old_end=str.length()-1;//原字符串的尾下标
        int new_end=str.length()-1+2*count;//新字符串的尾下标
        str.setLength(new_length);//对字符串的长度进行扩增
        while(old_end>0&&new_end>0){
            if(str.charAt(old_end)==' '){//遇到空格就替换
                str.setCharAt(new_end--,'0');
                str.setCharAt(new_end--,'2');
                str.setCharAt(new_end--,'%');
                old_end--;
            }
            else{
                //否则就把原字符移到新字符串的位置
                str.setCharAt(new_end--,str.charAt(old_end--));
            }
        }
        return str.toString();
    }

    public static void main(String[] args) {
        StringBuilder str = new StringBuilder("we are happy");
        String tem=replaceSpace(str);
        System.out.println(tem);
    }
//逆置单链表(栈)
      public ArrayList<Integer>printListFormTailToHead(ListNode listNode){
          Stack<Integer>stack=new Stack<>();
          ArrayList<Integer>list=new ArrayList<>();
          while(listNode!=null){
              stack.push(listNode.val);
              listNode=listNode.next;
          }
          while(!stack.isEmpty()){
              list.add(stack.pop());
          }
          return list;
      }
    //逆置单链表(双指针法)
    public ArrayList<Integer>printListFormTailToHead1(ListNode listNode){
        ArrayList<Integer>list=new ArrayList<>();
        while(listNode!=null){
            list.add(listNode.val);
            listNode=listNode.next;
        }
        int i=0;
        int j=list.size()-1;
        while(i<j){
            list.set(i,list.get(j));
            list.set(j,list.get(i));
            i++;
            j--;
        }
        return list;
    }

    //根据前序和中序遍历二叉树
    public TreeNode reConstructBinaryTreeCore(int []pre,int preStart,int preEnd,int []in,int inStart,int inEnd){
        if(preStart>preEnd||inStart>inEnd){
            return null;
        }
        TreeNode root=new TreeNode(pre[preStart]);
        for(int i=inStart;i<inEnd;i++){
            if(in[i]==pre[preStart]){
                root.left=reConstructBinaryTreeCore(pre,preStart,preStart+i-inStart,in,inStart,i-1);
                root.right=reConstructBinaryTreeCore(pre,preStart+i-inStart+1,preEnd,in,i+1,inEnd);
            }
        }
        return root;
    }
    public TreeNode reConstructBinaryTree(int []pre,int []in){
        if(pre.length==0||in.length==0){
            return null;
        }
       return reConstructBinaryTreeCore(pre,0,pre.length-1,in,0,in.length-1);
    }

    //求斐波那契数列(递归+map)-高效
    private Map<Integer,Integer>map=new HashMap<>();
      public int Fibonacci(int n){
        if(n==0||n==1){
            return n;
        }
        int tem=0;
        if(map.containsKey(n-2)){
            tem=map.get(n-2);
        }else{
            tem=Fibonacci(n-2);
            map.put(n-2,tem);
        }
        int tmp=0;
        if(map.containsKey(n-1)){
            tmp=map.get(n-1);
        }else{
            tmp=Fibonacci(n-1);
            map.put(n-1,tmp);
        }
        return tem+tmp;
    }
//青蛙跳台阶(第一种)
    public int JumpFloor(int target){
          if(target==0){
              return 1;
          }
          int []dp=new int [target+1];
          dp[0]=1;
          dp[1]=1;
          for(int i=2;i<target;i++){
              dp[i]=dp[i-1]+dp[i-2];
          }
          int num=dp[target];
          return num;
    }
    //青蛙跳台阶(第二种)
      public int JumpFloor1(int target){
          int first=1;
          int second=2;
          int third=0;
          while (target>2){
              third=first+second;
              first=second;
              second=third;
              target--;
          }
          return third;
      }
    //反转单链表(递归)
     /* public void printListFormTailToHeadHelper(ListNode listNode,ArrayList<Integer>list){
        if(listNode==null){
            return ;
        }
        printListFormTailToHeadHelper(listNode.next,list);
        list.add(listNode.val);
      }
      public ArrayList<Integer>printListFormTailToHead(ListNode lisNode){
          ArrayList<Integer>list=new ArrayList<>();
          printListFormTailToHeadHelper(listNode,list);
          return list;
      }*/
}
